package com.lfg.leetcode.leetcode0;

/**
 *
 */
public class No10RegMatch2 {

    private static String str = "";
    private static String pattern = "";

    public static boolean isMatch(String s, String p) {
        // 考虑几个特殊样例，比如两个都为空，pattern为空。
        if (s.equals(p)) {
            return true;
        }
        if (p.equals("")) {
            return false;
        }
        str = s;
        pattern = p;
        return match(0, 0);
    }

    public static boolean match(int index1, int index2) {
        boolean indexLast1 = index1 >= str.length();
        boolean indexLast2 = index2 >= pattern.length();
        // 当匹配到两个字符串的下标都到底的时候，匹配成功
        if (indexLast1 && indexLast2) {
            return true;
        }
        if (!indexLast1 && indexLast2) {
            return false;
        }

        // 第一种情况：pattern的下一个字符为*号时
        if (index2 + 1 < pattern.length() && pattern.charAt(index2 + 1) == '*') {
            if (indexLast1) {
                return match(index1, index2 + 2);
            }
            if (str.charAt(index1) == pattern.charAt(index2) || pattern.charAt(index2) == '.') {
                // 匹配str的下一个字符或者抛弃这个星号去匹配pattern下一个模式
                return match(index1 + 1, index2) || match(index1, index2 + 2);
            } else {
                return match(index1, index2 + 2);
            }
        }
        if (indexLast1) {
            return false;
        }
        // 第二种情况：pattern的下一个字符不为*，直接匹配单个字符
        if (str.charAt(index1) == pattern.charAt(index2) || pattern.charAt(index2) == '.') {
            return match(index1 + 1, index2 + 1);
        }
        return false;
    }

    public static boolean equals(String str, String pattern, int si, int pi) {
        if (pattern.charAt(pi) == '.') {
            return true;
        }
        if (str.charAt(si) == pattern.charAt(pi)) {
            return true;
        }
        return false;
    }

    public static void main(String[] args) {
//        System.out.println("aa" + isMatch("aa", "a"));
//        System.out.println("aab=" + isMatch("aab", "c*a*b"));
//        System.out.println("caab=" + isMatch("caab", "c*a*ba"));
//        System.out.println("ab=" + isMatch("ab", ".*"));
//        System.out.println("ab=" + isMatch("ab", ".*"));
//        System.out.println("aa" + isMatch("aa", "a*"));
//        System.out.println("aaa=" + isMatch("aaa", "a*a"));
//        System.out.println("mississippi=" + isMatch("mississippi", "mis*is*ip*."));
//        System.out.println("mississippi=" + isMatch("mississippi", "mis*is*p*."));
//        System.out.println("aaba=" + isMatch("aaba", "ab*a*c*a"));
        System.out.println("aaa=" + isMatch("aaa", "aaaa"));


    }


}
